package com.sjf.day02.Search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 插值查找算法
 *
 * @author <huangtang>
 * @since 2021/12/30 14:52
 **/
public class InsertValueSearch {

    public static void main(String[] args) {
        //int[] arr = new int[100];
        //
        //for (int i = 0; i < 100; i++) {
        //    arr[i] = i+1;
        //}
        int[] arr = {3,66,75,99,108,347,347,523};

        List<Integer> list = insertValueSearch2(arr, 0, arr.length - 1, 347);
        for (Integer integer : list) {
            System.out.println(integer +"："+arr[integer]);
        }
        //System.out.println(index +"："+arr[index]);
    }

    /**
     * 插值查找算法
     * @param arr     查找的数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找的值
     * @return  返回查找到的值的下标
     */
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        System.out.println("查找次数+1");
        if(left > right || findVal<arr[0] || findVal>arr[arr.length-1]){
            return -1;
        }

        //取到中间值的索引
        int mid = left + (right - left) * (findVal - arr[left])/(arr[right] - arr[left]);

        if(findVal > arr[mid]){
            //比中值大，向右递归
            return insertValueSearch(arr,mid+1,right,findVal);
        }else if(findVal < arr[mid]){
            //比中值小，向右递归
            return insertValueSearch(arr,left,mid-1,findVal);
        }else{
            //刚好就是中值，直接返回
            return mid;
        }
    }

    /**
     * 插值查找算法
     * @param arr     查找的数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找的值
     * @return  返回查找到的值的下标
     */
    public static List<Integer> insertValueSearch2(int[] arr, int left, int right, int findVal){
        System.out.println("查找次数+1");
        if(left > right || findVal<arr[0] || findVal>arr[arr.length-1]){
            return Collections.singletonList(-1);
        }

        //取到中间值的索引
        int mid = left + (right - left) * (findVal - arr[left])/(arr[right] - arr[left]);

        if(findVal > arr[mid]){
            //比中值大，向右递归
            return insertValueSearch2(arr,mid+1,right,findVal);
        }else if(findVal < arr[mid]){
            //比中值小，向右递归
            return insertValueSearch2(arr,left,mid-1,findVal);
        }else{
            List<Integer> resIndexList = new ArrayList<>();
            //向左寻找相同的值
            int temp = mid-1;
            while(true){
                if(left < 0 || arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp--);
            }
            resIndexList.add(mid);
            //向右寻找相同的值
            temp = mid +1;
            while(true){
                if(right > arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp++);
            }
            return resIndexList;
        }
    }
}
